package com.arron.algorithm.leetcodetop100.回溯;

import java.util.Arrays;

public class 不同路径II {

    int[][] mem;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //记忆一下已经搜索的节点的信息
        mem = new int[m][n];

        for (int[] ints : mem) {
            Arrays.fill(ints,-1);
        }

        //排除起点 和 终点为障碍物的可能
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){
            return 0;
        }

        return dfs(obstacleGrid,0,0);
    }

    private int dfs(int[][] grid, int i, int j) {

        // 排除越界的，和遇到障碍物的路径
        if (i < 0 || j<0||i>=grid.length || j >= grid[0].length|| grid[i][j] == 1){
            return 0;
        }

        if (mem[i][j]!=-1){
            return mem[i][j];
        }

        //最终到达终点的统计路径数
        if (i==grid.length-1 && j ==grid[0].length-1){
            return 1;
        }


        //去右边 ，下边
        int number =  dfs(grid,i+1,j) + dfs(grid,i,j+1);

        //记录一下已经搜索过的结果
        mem[i][j] = number;

        return mem[i][j];
    }
}
